/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年03月12日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int size = T.size();
        vector<int> res(size, 0);
        if(size == 0){
            return res;
        }

        stack<int> s;
        map<int, int> posmap;

        s.push(T[size - 1]);
        posmap[T[size-1]] = size - 1;

        for(int i = size - 2; i >= 0; i--){
            while(!s.empty() && T[i] >= s.top()){
                s.pop();
            }

            if(!s.empty()){
                res[i] = posmap[s.top()] - i;
            }

            s.push(T[i]);
            posmap[T[i]] = i;
        }

        return res;
    }
};




class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int size = T.size();
        vector<int> res(size, 0);
        if(size == 0){
            return res;
        }

        stack<int> s;
        s.push(size - 1);

        for(int i = size - 2; i >= 0; i--){
            while(!s.empty() && T[i] >= T[s.top()]){
                s.pop();
            }
            
            if(!s.empty()){
                res[i] = s.top() - i;
            }
            s.push(i);
        }

        return res;
    }
};
